#ifndef SWORD2OFFER_H_
#define SWORD2OFFER_H_
#include <iostream>
int count1s(int n) {
	int count = 0;
	while (n) {
		n = n & (n - 1);
		++count;
	}
	return count;
}

int mypow(int base, int power) {

	if (!base)
		return 0;


	int p = 1, fact = base;
	while (power) {
		if (power & 0x1) {
			p *= fact;
		}
		fact *= fact;
		power >>= 1;
	}
	return p;
}
void testCount1s() {
	int a = 0xfa;
	std::cout << count1s(a) << std::endl;
}

void testPow() {
	int s = mypow(2, 10);
	std::cout << "result is " << s << std::endl;
}

struct ListNode {
	int value;
	ListNode *next;
};

ListNode *mergeOrderedList(ListNode *list1, ListNode *list2) {
	ListNode *p, *h1 = list1, *h2 = list1;
	p = (h1->value < h2->value) ? h1 : h2;
	ListNode *head = p;
	while (h1 || h2) {
		if (h1 && ((h2 && h1->value < h2->value) || !h2)) {
			ListNode *temp = h1;
			h1 = h1->next;
			p->next = temp;
			p = p->next;
			continue;
		}
		if (h2 && (!h1 || (h1 && h1->value >= h2->value))) {
			ListNode *temp = h2;
			h2 = h2->next;
			p->next = temp;
			p = p->next;
			continue;
		}
	}
	return head;
}

struct ComplexListNode {
	int value;
	ComplexListNode *next;
	ComplexListNode *sibling;
};

void CloneNodes(ComplexListNode *pHead) {
	ComplexListNode *pNode = pHead;
	while (pNode != nullptr) {
		ComplexListNode *pCloned = new ComplexListNode();
		pCloned->value = pNode->value;
		pCloned->next = pNode->next;
		pCloned->sibling = nullptr;

		pNode->next = pCloned;
		pNode = pCloned->next;
	}
}

void ConnectSiblingNodes(ComplexListNode *pHead) {
	ComplexListNode *pNode = pHead;
	while (pNode) {
		ComplexListNode *pCloned = pNode->next;
		if (pNode->sibling) {
			pCloned->sibling = pNode->sibling->next;
		}
		pNode = pCloned->next;
	}
}

ComplexListNode *ReconnectNodes(ComplexListNode *pHead) {
	return nullptr;
}

struct BinaryTreeNode {
	int value;
	BinaryTreeNode *left;
	BinaryTreeNode *right;
};
void convertNode(BinaryTreeNode *pNode, BinaryTreeNode ** last) {
	if (!pNode)
		return;
	BinaryTreeNode *pCurrent = pNode;
	if (pCurrent->left)
		convertNode(pCurrent->left, last);
	pCurrent->left = *last;
	if (*last)
		(*last)->right = pCurrent;
	*last = pCurrent;
	if (pCurrent->right)
		convertNode(pCurrent->right, last);
}

BinaryTreeNode *Convert(BinaryTreeNode *root) {
	BinaryTreeNode *last = nullptr;
	convertNode(root, &last);
	BinaryTreeNode *head = last;
	while (head && head->left) {
		head = head->left;
	}
	return head;
}

void permutation(char *str, char *begin);
void permutation(char *str) {
	if (!str)
		return;
	permutation(str, str);
}
#include <ctime>

void permutation(char *str, char *begin) {
	if (*begin == '\0')
		printf("%s\n", str);
	else {
		for (char *pCh = begin; *pCh != '\0'; pCh++) {
			char temp = *pCh;
			*pCh = *begin;
			*begin = temp;
			permutation(str, begin + 1);

			temp = *pCh;
			*pCh = *begin;
			*begin = temp;
		}
	}
}

int partition(int *data, int length, int start, int end) {
	//int index = 
	std::srand(std::time(0));
	int rand = std::rand();
	int index = start + std::rand() % (end - start + 1);
	//int index = 3;
	//index = start - 1;
	std::swap(data[index], data[end]);
	int small = start - 1;
	for (index = start; index < end; ++index) {
		if (data[index] < data[end]) {
			++small;
			if (small != index)
				std::swap(data[index], data[small]);
		}
	}

	++small;
	std::swap(data[small], data[end]);
	return small;
}

int mypartition(int *data, int length, int begin, int end) {
	std::srand(std::time(0));
	int index = begin + std::rand() % (end - begin);

	std::swap(data[index], data[end - 1]);
	int i = begin - 1;
	int x = data[end - 1];
	for (int j = begin; j < end; ++j) {
		if (data[j] < x) {
			std::swap(data[++i], data[j]);
		}
	}
	std::swap(data[++i], data[end - 1]);
	return i;
}
void quickSort(int *data, int length, int start, int end) {
	if (end - start < 2)
		return;
	int p = mypartition(data, length, start, end);
	if (p > start)
		quickSort(data, length, start, p);
	if (p < end)
		quickSort(data, length, p + 1, end);
}
void testSwap() {
	int a = 5, b = 1;
	printf("a is %d and b is %d\n", a, b);
	std::swap(a, b);
	printf("a is %d and b is %d\n", a, b);
}
void testQuickSort() {
	int data[] = { 1,5,2,4,3, 10, 2, 8 ,7 };
	quickSort(data, 9, 0, 9);
	for (int i = 0; i < 9; ++i)
		std::cout << data[i] << " ";
	std::cout << std::endl;

	/*std::srand(std::time(0));
	int r = std::rand();
	int length = 20;
	int index = std::rand() % length;
	std::cout << "index of " << length << " is " << index << std::endl;*/
}
void testPartition() {
	int data[] = { 1,5,2,4,3, 10, 2, 8 ,7 };
	partition(data, 9, 0, 9);
	for (int i = 0; i < 9; ++i)
		std::cout << data[i] << " ";
	std::cout << std::endl;
}
void matrixProduct(int **a, int **b, int m, int n, int p) {

}
#endif